package leetcode_1_200;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeeCode_138 {
    public static void main(String[] args) {
        Node l7 = new Node(7);
        Node l13 = new Node(13);
        Node l11 = new Node(11);
        Node l10 = new Node(10);
        Node l1 = new Node(1);
        l7.next = l13;
        l7.random = null;
        l13.next = l11;
        l13.random = l7;
        l11.next = l10;
        l11.random = l1;
        l10.next = l1;
        l10.random = l11;
        l1.random = l7;
        System.out.println(copyRandomList(l7));
    }

    private static Node copyRandomList(Node head) {
        Map<Integer, Node> exists = new HashMap<>();
        Map<Node, Integer> toIndex = new HashMap<>();
        Node f = f(head, exists, 0, toIndex);
        return f;
    }

    private static Node f(Node root, Map<Integer, Node> exists, int n, Map<Node, Integer> toIndex){
        if (root == null)
            return null;
        if (n != -1 && exists.containsKey(n))
            return exists.get(n);
        Node newN = new Node(root.val);
        if (n != -1) {
            exists.put(n, newN);
            toIndex.put(root, n);
        }
        if (n == -1){
            Integer index = toIndex.get(root);
            return exists.get(index);
        }
        newN.next = f(root.next, exists, n + 1, toIndex);
        newN.random = f(root.random, exists, -1, toIndex);
        return newN;
    }

    private static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
